Content-addressed memories, sometimes known as associative memories, are well known in the prior art. Whereas conventional location-addressable memory is designed to retrieve data from a specific address, a content-addressable memory system finds and retrieves a collection of closely related data, called a record, by comparing a keyword value known to be associated with or located within the desired data with the data stored in the content-addressed memory. Once a match is found, the rest of the record can be accessed. Thus, all records containing one or more of the keyword values will be found without any prior knowledge of where the records are stored.
Whereas any memory is searchable for keyword values by sequentially reading and matching the words in the memory with the keyword value, the records of a content-addressed memory are searched simultaneously and in parallel for a match. The word cells are arranged in parallel and share a common data bus so that the keyword value can be sent simultaneously to all the word cells. The speed with which a content-addressed memory finds all records matching a keyword value is, consequently, significantly faster.
For example, if a court's written opinion is a record of the content-addressed memory, it may be found by searching for the names of the parties in the suit. The names of the parties are the keyword values. The name of a party in this example is always stored in a particular area of the record, called a field or subfield; the name of the case is the value. Thus, a keyword value defines a particular field or subfield and a particular value. Only a particular area of all records stored in the content-addressed memories need, therefore, be searched and compared with a particular keyword value. Several keyword values, called keyword value combinations, may also be used to find the desired record or records.
A typical application of a content-addressable memory is a cache memory. Instead of having to retrieve data stored in a large main memory, frequently used data is stored in a smaller content-addressable memory, thus permitting quicker retrieval. Each word cell contains a record and a corresponding address in the main memory. With this address as a keyword value, the record is retrievable from the cache memory by asking it, in effect, for the record having that address, no matter where it is actually stored within the memory.
In storing and quickly retrieving large amounts of data, prior art content-addressed memories are presented with several physical limitations. In order to store large records, either the word cells need to be made very large, or the record must be stored in a separate "numbered-cell" storage where the keyword value is mapped to the address of the "numbered cell." The disadvantage of the first technique is that the size of the word cells are fixed and large, at least large enough to accommodate all the necessary values of its foreseeable use. Content-addressed memories, thus, must either be individually tailored to specific uses, making high-volume production techniques unavailable to reduce costs, or there will be wasted storage space. The numbered-cell technique, on the other hand, taxes the speed of the memory when more than one keyword value is used to retrieve a record. Instead of storing the entire record in the content-addressed memory, it is stored in a "numbered cell" memory, with the number, or address, of the cell stored in the content-addressed memory, along with a few selected keyword values. Once a match is made, the number, or address, of the record is read, and the record of interest is accessed. After a list of records satisfying a first keyword value is found, however, the records on the list are matched sequentially with other keyword values to find desired subsets of the matched records, since each record must be individually read and matched from the main memory. A significant time penalty is, thus, imposed for matching combinations of keyword values.
There is a need, therefore, for a content-addressed memory that permits the flexibility of storing records of any desired size and quickly accessing the records with keyword value combinations.